This invention relates to embedding messages in a halftoned digital image with an error diffuison technique.
Digital halftoning is a technique employing digital image processing to produce a halftoned input digital image from an input digital image. An input digital image normally consists of pixels of discrete values typically ranging from 0 to 255. To reproduce this image on an output device capable of printing dots of one gray level (e.g. black), it is necessary to convert the input digital image to a halftoned digital image using some form of halftoning techniques. Halftoning methods rely on the fact that an observer""s eye will spatially average over some local area of the halftoned digital image so that intermediate gray levels can be created by turning some of the pixels xe2x80x9conxe2x80x9d and some of the pixels xe2x80x9coffxe2x80x9d in some small region of the halftoned digital image. The fraction of the pixels that are turned on will determine the apparent gray level. Common prior art methods of digital halftoning include error diffusion and dithering (see R. Ulichney, xe2x80x9cDigital Halftoning,xe2x80x9d MIT Press, Cambridge, Mass., 1987).
Error diffusion is an adaptive algorithm that produces patterns with different spatial frequency content depending on the input digital image value. FIG. 1 shows a prior art block diagram depicting a basic error diffusion technique. This technique is disclosed in more detail in xe2x80x9cAn Adaptive Algorithm for Spatial Greyscale,xe2x80x9d Proceedings of the Society for Information Display, volume 17, pp. 75, 1976 by R. W. Floyd and L. Steinberg. For purpose of illustration it will be assumed that the pixels of the input digital image span the range from 0 to 255. As shown in FIG. 1, the pixels of an input digital image are thresholded in block 10 to produce thresholded pixels. The block 10 provides a signal having a 0 for any pixel of the input digital image below the threshold, and a 255 for any pixel of the input digital image above the threshold. A difference signal generator 12 receives the signal representing the pixel of the input digital image from block 10 and also from the output of an adder 16, which will be discussed later. The difference signal generator 12 produces a difference signal representing the error introduced by the thresholding process. The difference signal is multiplied by a series of error feedback weights in a error feedback 14, and is provided to the adder 16 which adds the weighted difference signal to the nearby pixels that have yet to be processed. This insures that the arithmetic mean of the pixels of the halftone digital image is preserved over a local image region.
FIG. 2 illustrates how a typical error can affect neighboring pixels in a halftoned digital image. The halftoned digital image from error diffusion is generally considered to be of high quality, since most of the halftone noise is distributed in a high spatial frequency band where human visual sensitivity is relatively low.
An artifact that is typically associated with error diffusion halftoning technique is known as xe2x80x9cworms.xe2x80x9d Worms are formed when the black or white pixels of a halftoned digital image appear to string together in an area that should be otherwise uniform. Uniform image regions of certain gray levels, i.e., highlight regions, are especially susceptible to xe2x80x9cwormxe2x80x9d artifacts.
One much desired requirement for the usage of digital images is the detection of the unauthorized use of copyrighted or personal images. For example, the professional photographers are greatly concerned about the illegitimate use of their copyrighted images in the recent years. As the use of Internet and digital imaging devices become more popular, this concern is increasingly shared by common consumers. One example of the methods developed for this purpose is disclosed in commonly assigned U.S. Pat. No. 5,822,660.
An object of the present invention is to efficiently halftone digital images while embedding messages in such halftoned digital images at the same time.
This object is achieved by a method of producing a halftoned digital image having an embedded message, comprising the steps of:
a) using a digital message and at least one digital carrier image to produce a scrambled message image; and
b) halftoning the digital image employing an error diffusion process where noise is added to the digital image, the noise including the scrambled message image.
This object is further achieved by a method for embedding a message in a halftoned digital image, comprising the steps of:
a) receiving an input digital image having a plurality of pixels;
b) providing a digital message image having pixels representing the message to be embedded;
c) providing a digital carrier image which has a random distribution of pixel values;
d) using the digital message image and the digital carrier image to produce a scrambled message image; and
e) halftoning the input digital image employing an error diffusion process where noise is added to the input digital image, the noise includes the scrambled message image, whereby the scrambled message image is embedded in the halftoned digital image.
An advantage of the present invention is that the efficiency of halftoning an input digital images and embedding information in the halftoned digital image is improved. Information can be embedded in the halftoned digital image and xe2x80x9cwormxe2x80x9d artifacts can be minimized in the halftoned digital image at the same time.
The halftoned digital images can be printed or displayed. A feature of embedding messages in the printed or displayed images is that the messages can subsequently be extracted later for proofing the authentication of the image or for detecting the unauthorized use of the image.